#include <memory>
#include <iostream>
#include <string>

struct Node{
	int key;
	std::shared_ptr<Node> left, right, parent;
	~Node() { std::cout << "Node " << key << " is destructed\n"; }
};

std::string preorder_serialize(const std::shared_ptr<Node>& root);
std::shared_ptr<Node> preorder_deserialize(std::string str) ;

std::string bfs(const std::shared_ptr<Node> &root);
std::string level_order_2queue(const std::shared_ptr<Node> &root);
std::string level_order_1queue(const std::shared_ptr<Node> &root);
int height(const std::shared_ptr<Node>& node);
int bfs_height(const std::shared_ptr<Node> &root);

void print_tree(const std::shared_ptr<Node>& root, std::ostream& out = std::cout) ;